package algorithms

import (
	"cmp"
	"fmt"
)

// 链表中每个子节点结构
type ListNode[T cmp.Ordered] struct {
	Value T
	Prev  *ListNode[T]
	Next  *ListNode[T]
}

// 链表结构
type DoubleList[T cmp.Ordered] struct {
	Head   *ListNode[T]
	Tail   *ListNode[T]
	Length int
}

// 正序遍历
func (list *DoubleList[T]) Traverse() {
	curr := list.Head //

	for curr != nil {
		fmt.Println(curr.Value)
		curr = curr.Next
	}

	fmt.Println("")
}

// 逆序遍历
func (list *DoubleList[T]) ReverseTraverse() {
	curr := list.Tail

	for curr != nil {
		fmt.Println(curr.Value)
		curr = curr.Prev
	}

	fmt.Println("")
}

// 头插入 [ 如果要在全局层面修改成员变量，传入的时候需要带上 * 指针 ]
func (list *DoubleList[T]) PushFront(x T) {
	node := &ListNode[T]{Value: x}

	head := list.Head
	if head == nil {
		// 如果是空的 新元素既是首也是尾
		list.Tail = node
		list.Head = node
	} else {
		head.Prev = node // head 是原头, 将原头的 Prev 改为新元素指针
		node.Next = head // 当前元素的 Next 改为原头
		list.Head = node // 链表头改为新元素指针
	}
	list.Length += 1
}

// 向尾部追加元素 [ 如果要在全局层面修改成员变量，传入的时候需要带上 * 指针 ]
func (list *DoubleList[T]) PushBack(x T) {
	node := &ListNode[T]{Value: x}

	tail := list.Tail
	if tail == nil {
		// 如果是空的 新元素既是首也是尾
		list.Head = node
		list.Tail = node
	} else {
		tail.Next = node // tail 是原尾, 将原尾的 Next 改为新元素指针
		node.Prev = tail // 当前元素的 Prev 改为原头
		list.Tail = node // 链表尾改为新元素指针
	}

	list.Length += 1
}

// 获取 list 中的某个元素
func (list *DoubleList[T]) GetRandom(idx int) *ListNode[T] {
	if idx < 0 || idx >= list.Length {
		return nil
	}

	curr := list.Head
	for i := 0; i < idx; i++ {
		curr = curr.Next
	}

	return curr
}

// 指定某个元素之后插入一个新元素
func (list *DoubleList[T]) InsertByAfter(x T, byNode *ListNode[T]) {
	newNode := &ListNode[T]{Value: x}

	if byNode.Next != nil {
		beforeNextNode := byNode.Next
		beforeNextNode.Prev = newNode
		newNode.Next = beforeNextNode
	} else {
		list.Tail = newNode
	}

	byNode.Next = newNode
	newNode.Prev = byNode
	list.Length += 1
}

// 指定某个元素之前插入一个新元素
func (list *DoubleList[T]) InsertByBefore(x T, byNode *ListNode[T]) {
	newNode := &ListNode[T]{Value: x}

	if byNode.Prev != nil {
		beforePrevNode := byNode.Prev
		beforePrevNode.Next = newNode
		newNode.Prev = beforePrevNode
	} else {
		list.Head = newNode
	}
	byNode.Prev = newNode
	newNode.Next = byNode
	list.Length += 1
}
